
\documentclass{article}

% Paquetes que se van a usar
% --------------------------
\usepackage{placeins}
\usepackage[latin1]{inputenc}
\usepackage{fancyhdr}
%\usepackage{amsfonts}
\usepackage{graphicx}
\usepackage{verbatim}
%\usepackage{array}
\usepackage{alltt}
\usepackage{moreverb}

% Configuracion de margenes
% -------------------------

\oddsidemargin   0pt
\evensidemargin  0pt
\textwidth       440pt
\textheight      660pt
\headheight      10pt
\topmargin       0pt
\headsep         20pt

\pagestyle{fancy}

\renewcommand{\contentsname}{Indice}

\rhead{\textsc{Estructuras de Datos y Algoritmos}}
\lhead{ITBA}

\setlength{\parindent}{0pt}
\setlength{\parskip}{5pt}

\title{\textbf{Trabajo Especial \\Estructuras de Datos y Algoritmos}}

\author{
Alvarez, Tom\'as \\
Micciullo, Maximiliano\\
Modernell, Dami\'an\\ \\
INSTITUTO TECNOLOGICO DE BUENOS AIRES}
\date{\today}

\makeindex

% Empieza el documento.
\begin{document}
\maketitle

\tableofcontents
\newpage

% Introduccion
\section{Introducci\'on}

En el presente informe se encuentra el desarrollo de una aplicaci\'on que provee las herramientas b\'asicas para 
gestionar un proyecto. Esta aplicaci\'on cuenta con las principales tres capas que son planeamiento, programaci\'on y
control de un proyecto. \\

En un pantallaso r\'apido de cada capa, la primera hace referencia a la divici\'on del proyecto en actividades,
determinando el tiempo necesario para ejecutarlas y las precedencias que existen entre ellas. La segunda etapa,
determina los tiempos m\'as tempranos de inicio y finalizaci\'on de actividades, tiempos m\'as tardios de inicio y
finalizaci\'on de las actividades, holguras de tiempos disponibles, actividades cr\'iticas, camino cr\'itico (CPM) y
el programa de tiempos de ocurrencia de eventos y de ejecuci\'on de actividades. Por \'ultimo se encuentra la capa de
control, donde la aplicaci\'on eval\'ua el cumplimiento de lo establecido en las capas anteriores. Esto lo realiza
permitiendo ejecutar modificaciones sobre el diagrama de actividades y otorgando el rec\'alculo de tiempos y actividades
cr\'iticas. \\

La aplicaci\'on brinda el manejo de las tres capas de forma muy simple e intuitiva para que el usuario pueda construir
su proyecto en poco tiempo. Brinda una visualizaci\'on de la red de actividades en formato png y un calendario mostrando
las fechas de ejecuci\'on m\'as temprana de cada actividad del proyecto. \\

% Desarrollo
\section{Desarrollo}

A continuaci\'on se exponenlos m\'odulos que componen a la aplicaci\'on de gesti\'on y se explica su principal funcionamiento. \\

\subsection{Front End}

La forma de instalar la aplicaci\'on es ejecutando el comando "make gestion", as\'i se crea en su entorno de trabajo un
ejecutable llamado \"gesti\'on\", el cual al correrlo da comienzo de la aplicaci\'on. \\

Al comienzo de la aplicacio\'on se puede ver un men\'u con las siguientes 4 opciones: 
\begin{itemize}
\item Ingresar un archivo con una tabla de actividades.
\item Ingresar modificaciones a una red.
\item Obtener el calendario de actividades del proyecto para una fecha de inicio determinada.
\item Obtener una representaci\'on gr\'afica de la red.
\end{itemize}

A medida que se ingresa en cada una de estas opciones se despliegan otros menues dandole al usuario m\'as opciones de
modificacion de su red. Como por ejemplo modificar la duraci\'on, descripci\'on y precedencias de un actividad ya establecida.
Eliminar una actividad de la red, o insertar una nueva actividad en la red. \\

La opci\'on de obtener una representaci\'on gr\'afica de la red, genera un gr\'afico de la red Pert mostrando todas sus
actividades con sus respectivos tiempos promedio de duraci\'on, sus precedencias y los caminos cr\'iticos encontrados (marcados
en color rojo). Las l\'ineas punteadas en color rojo representan actividades ficticias, necesarias para mantener precedencias
entre actividades. Esta representaci\'on gr\'afica queda almacenada en un archivo llamado "graph.png" el cual se puede
consultar con cualquier editor de im\'agenes. \\

\subsection{Back End}

Se desarroll\'o el TAD PERT, el cual contiene como contrato todas las funciones necesarias para poder establecer el correcto
funcionamiento del aplicativo gesti\'on. A continuaci\'on se muestran las principales funciones de contrato del TAD PERT
indicando su forma de implementaci\'on y mencionando los TADs auxiliares necesarios para su desarrollo. \\

% Modulos disenados
\section{M\'odulo dise\~nado}

\subsection{TAD PERT}

Se defini\'o como tipo de dato oculto al usuario del TAD la estructura pertCDT la cual contiene los siguientes campos:

\begin{itemize}
\item digraphADT digraph
\item queueADT cola
\item actividadT *vecActivities
\item nodesActivity *vecNodes
\item nodesActivity *vecFic
\item int cant
\item int bloque
\end{itemize}

Donde digraphADT y queueADT hacen referencia a TADs auxiliares que luego se comentar\'an en dicho informe. \\

actividadT es una estructura que contiene toda la informaci\'on necesaria para crear una actividad en la red PERT.
Entre sus campos a destacar est\'an el ID de la tarea, como la duraci\'on, descripci\'on, margen o holgura, tiempo m\'as
cercano de terminaci\'on, tiempo mas tard\'io de terminacion, un tag para ver si fue visitada la arista y un vector de
ints que contiene las actividades precedentes a esta actividad. vecActivities fue creado para almacenar en un arreglo
todas las actividades de la red con esta informaci\'on y poder consultarla, modificarla, elminar e insertar actividades
en cualquier momento del desarrollo del TAD. \\

nodesActivity es una estructura creada para establecer informaci\'on de los nodos presentes entre las actividades.
Entre sus campos se destacan: nodoInicio que almacena el nodo inicial de una actividad. nodoFin, el correspondiente
para el nodo final de una actividad. Y logicErase, valor que informa si la actividad tiene un borrado l\'ogico o no.
Se desidi\'o crear el arrego vecNodes con el fin de llevar la informaci\'on de las actividades en forma ordenada. Este arreglo
cumple la funci\'on de indexar en el arreglo de actividades cuando es necesario modificar, insertar o eliminar una actividad, 
como tambi\'en para su consulta. \\

vecFic es un arreglo muy similar al anterior pero almacena informaci\'on sobre las actividades ficticias. Su prop\'osito se
debe a que es necesario conocer donde se encuentran dichar aristas en casos de inserci\'on, borrado y modificacion de actividades. \\

cant es un entero que informa la cantidad de actividades que hay en el arreglo de actividades y bloque informa sobre la memoria alocada
que posee el arreglo de actividades.

A continuaci\'on se muestran las funciones del contrato TAD PERT:

\begin{itemize}
\item LoadPert: Es la encargada de crear la representaci\'on en memoria del digrafo que establece la red PERT. Para esto
necesita conocer el archivo que contiene las especificaciones iniciales de la red. Utiliza funciones de parser para poder
obtener los datos contenidos en el archivo. Trabaja en forma secuencial, a medida que se obtienen los datos del archivo 
se van creando las actividades en el digrafo. Tiene como par\'ametro de salida un pertADT con toda la informaci\'on de
la red creada.

\item GetCPM: Funci\'on encargada de obtener el camino m\'inimo de la red (CPM). Para ello utiliza tres funciones recursivas
para poder establecer los tiempos tempranos, tardios y margenes de las actividades. Estas son CalcEarlyTimes, CalcLateTimes y
CalcMargins. Luego iterando por el digrafo, con un patr\'on iterador por nodos, se va marcando las actividades visitadas y
calculando cuales correspondes al CPM.

\item CalcEarlyTimes: Encargada de calcular los tiempos tempranos de la red. Utiliza un patr\'on iterador por nodos para
navegar el digrafo y se llama en forma recursiva. Va dejando la informaci\'on obtenida en los nodos de la red

\item CalcLateTimes: Tiene como funcion calcular los tiempos tard\'ios de la red. Tamb\'en utiliza el patr\'on iterador por
nodos para navegar el digrafo y se llama en forma recursiva. Va dejando la informaci\'on obtenida en las aristas de la red.

\item CalcMargins: Se encarga de calcular los m\'argenes o holguras de la red PERT, para luego poder calcular el camino 
cr\'itico. Se llama en forma recursiva desde el primer nodo de la red y deja la informaci\'on en las aristas de la red.

\item CreateDotFile: Se encarga de generar un archivo ".dot" para poder representar la red en forma gr\'afica. Para esto
utiliza la biblioteca "graphviz" y a medida que va recorriendo el digrafo genera la sintaxis necesaria para la creaci\'on
de la imagen de la red PERT.

\item Calendar: Dada una fecha de comienzo ingresada por el usuario se encarga de establecer fechas a todas las actividades
de la red. Contempla cualquier tipo de fecha, entre ellas a\~nos bisiestos. El formato de entrada de la fecha se especifica
en el men\'u para que el usuario pueda saber como ingresarla. Genera como salida un archivo que contiene toda la informaci\'on
de las actividades con sus respectivas fechas.

\item InsertTask: Funci\'on encargada de insertar una nueva actividad en la red. Se le solicita al usuario que ingrese 
la informaci\'on necesaria de la actividad y si es posible se inserta la actividad en la red. Para esto se chequean casos
donde sea posible insertar la actividad debido a las precedencias ya establecidas en la red. En caso de no poder insertarse
se informa al usuario por salida de error. Si fue insertada con \'exito se vuelve a recalcular todos los tiempos y margenes de la red.

\item ModifyTask: Funcion encargada de modificar una actividad ya presente en la red. Para esto se le solicita al usuario
que ingrese cual es la modificacion que pretende hacer. Entre ellas la duraci\'on, descripci\'on o precedencia de una actividad.
Se modifica los datos de la actividad siempre y cuando sea posible, debido a que puede quedar desconectada la red o cambiar precedencias
de tareas anteriores. Para esto se busca cual es la actividad a modificar y se estudia el caso. En caso de no ser posible modificar
dicha actividad se le informa al usuario. Si fue modificada con \'exito se vuelve a recalcular nuevamente los tiempos y margenes de toda la red.

\item DeleteTask: Encarga de la eliminacion de una actividad. Puede realizarce la eliminaci\'on siempre y cuando la tarea no sea 
una tarea cr\'itica o se modifique las precedencias de otras tareas ya establecidas en la red. En caso de error se le informa al usuario y en
caso de exito la arista deja de exitir en la representaci\'on, pero en realidad queda borrada l\'ogicamente en el algoritmo. Una vez eliminada
se recalculan los tiempos y margenes nuevamente.

\item FreePert: Funci\'on de liberaci\'on de toda la estructura almacenada en memoria del TAD PERT. Una vez invocada no se pueden
utilizar m\'as las funciones del contrato.
\end{itemize}

Hay que destacar que el digrafo que representa a la red PERT se crea una \'unica vez, por lo tanto siempre que se realice una insertci\'on,
modificaci\'on o eliminaci\'on de una actividad se realiza sobre la misma representaci\'on y no se crea una nueva.\\


% Modulos Auxiliares
\section{M\'odulo auxiliares}

\subsection{TAD Digraph}
A partir de la implementaci\'on realizada en las clases de la c\'atedra respecto del TAD grafo, se procedi\'o a realizar
la implementaci\'on del TAD digraph. B\'asicamente cumple con las mismas funciones de contrato que el anteriormente mencionado
y adem\'as con la implementaci\'on de patrones iteradores por aristas, nodos y BFS. La estructura utiliza es la de listas de listas;
donde la primer lista corresponde a los nodos y la segunda a la representaci\'on de la aristas. Como es dirigido en ella solo se encuentran
las aristas que salen del nodo y no las que llegan a \'el.

\subsection{TAD Queue}
A partir de la representaci\'on que brinda el texto de Roberts, se gener\'o dicho TAD implementado con una lista con header.
Dicho TAD brinda las principales operaciones de una cola como: crearla, liberarla, encolar, desencolar, chequear si la cola
esta vac\'ia, llena y la cantidad de elementos que esta posee.

% Testeos
\section{Testeos}

La forma de trabajar fue generar 4 archivos de entrada para la red. Entre ellos se encontraban redes b\'asicas hasta redes m\'as
complejas. Complejas en el sentido de su representaci\'on. \\

A medida que se ibam generando las principales funciones del TAD PERT, se corroboraba su correcto funcionamiento creando una funci\'on
de testeo que utilizara estos 4 archivos mencionados y luego se chequeaba su correcto funcionamiento a partir del Plot observando el archivo
"graph.png". \\

Por \'ultimo, al finalizar todas las funciones, se testi\'o el correcto funcionamiento del men\'u de usuario con la utilizaci\'on de todas las opciones,
y chequeo de archivo de calendario y archivo de imagen de la red.\\

% Limitaciones y extensiones
\section{Limitaciones y Extensiones}

El proyecto presenta como limitaciones en la inserci\'on, borrado y modificacion de actividades.
En la insercion de actividades, solo se insertaran actividades que posean una unica precedencia y una unica sucesora. Esto se debe a que la implementacion para hacerlo para n precedencias y n sucesoras complejizaba el codigo en demasia.
En el borrado de actividades, No se borraran actividades que esten en caminos cr\'iticos, ni tampoco se borraran aquellas actividades cuyo grado de salida del nodo de inicio de la misma  sea igual a uno. Esto es debido a que el digrafo no esta implementado con listas doblemente encadenadas, y por lo tanto se complicaba en la implementacion chequear las aristas que llegaban a dicho nodo de inicio, en el caso de que fueran ficticias o no.
En La modificacion de precedencias, tambien son solamente aceptadas la modificacion para una sola precedencia y en algunas ocaciones tiene fallas que no pudimos solucionar por falta de tiempo.
. \\

Las extensiones que podr\'ian realizarce es brindar un men\'u mucho m\'as amigable implementandolo en alg\'un lenguaje visual, utilizando el mismo Back End.
Como tambi\'en quiza dar la opci\'on de almacenar la red PERT generada desde el men\'u.

%bibliografia
\section{Bibliograf\'ia y Links}
\begin{itemize}

	\item{CPM - PERT, Apunte aportado por la c\'atedra. 2008}\\
	
	\item{Kit del Dibujante - Visualizaci\'on de gr\'aficos con Graphviz, www.linux-magazine.es , 2008}\\
	
	\item{El Lenguaje de Programaci\'on C, Brian Kernighan, Dennis Ritchie, Prentice Hall, 
		1988}\\

	\item{Programming Abstractions in C: A Second Course in Computer Science, Eric Roberts,
		Addison-Wesley Longman Publishing Co, 1997} \\
		
\end{itemize}

% Codigo fuente

%\section{C\'odigo fuente}
%A continuaci\'on se presentan todos los c\'odigos fuentes implementados: \\

%\subsection{frontend.c}
% frontend.c
%\small
%\verbatimtabinput[5]{frontend.c}

%imgADT.h
%\subsection{imgADT.h}
%\small
%\verbatimtabinput[5]{img.h}

%imgADT.c
%\subsection{imgADT.c}
%\small
%\verbatimtabinput[5]{img.c}

%quadtreeADT.h
%\subsection{quadtreeADT.h}
%\small
%\verbatimtabinput[5]{quadtree.h}

%quadtreeADT.c
%\subsection{quadtreeADT.c}
%\small
%\verbatimtabinput[5]{quadtree.c}

%bitmapADT.h
%\subsection{bitmapADT.h}
%\small
%\verbatimtabinput[5]{bitmap.h}

%bitmapADT.c
%\subsection{bitmapADT.c}
%\small
%\verbatimtabinput[5]{bitmap.c}

%commandADT.h
%\subsection{commandADT.h}
%\small
%\verbatimtabinput[5]{command.h}

%commandADT.c
%\subsection{commandADT.c}
%\small
%\verbatimtabinput[5]{command.c}

%hashADT.h
%\subsection{hashADT.h}
%\small
%\verbatimtabinput[5]{hash.h}

%hashADT.c
%\subsection{hashADT.c}
%\small
%\verbatimtabinput[5]{hash.c}

%listADT.h
%\subsection{listADT.h}
%\small
%\verbatimtabinput[5]{list.h}

%listADT.c
%\subsection{listADT.c}
%\small
%\verbatimtabinput[5]{list.c}

\end{document}
